/*
题目: 和为goal的二元子数组
给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。

子数组 是数组的一段连续部分。
https://leetcode.cn/problems/binary-subarrays-with-sum/
 */
public class NumSubarraysWithSum {
    public int numSubarraysWithSum(int[] nums, int goal) {
        // 前缀和 + 哈希表
        // 存在和为 Key 的路径 Value 条
        Map<Integer, Integer> map = new HashMap<> ();
        map.put(0, 1);
        int n = nums.length;

        int src = 0;
        int sum = 0;
        for (int i = 0; i < n; i ++) {
            sum += nums[i];
            src += map.getOrDefault(sum - goal, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return src;
    }
}
